package leetcode;

import leetcode.vo.ListNode;

import java.util.*;

public class MergeSortedLists {

    public static void main(String[] args) {
        MergeSortedLists m = new MergeSortedLists();
        ListNode n1 = new ListNode();
        n1.val = -2;
        ListNode n2 = new ListNode();
        n2.val = -1;
        ListNode n3 = new ListNode();
        n3.val = -1;
        n1.next = n2;
        n2.next = n3;

        ListNode n11 = new ListNode();
        n11.val = 1;
        ListNode n12 = new ListNode();
        n12.val = 6;
        ListNode n13 = new ListNode();
        n13.val = 9;
        n11.next = n12;
        n12.next = n13;

        ListNode[] lists = new ListNode[]{n1, n11};

        ListNode listNode = m.mergeKPartitionwoLists(lists, 0, lists.length - 1);
        System.out.println(listNode);
    }

    public ListNode mergeKPartitionwoLists(ListNode[] lists, int start,int end) {
        if(start == end) return lists[start];
        if(start > end) return null;
        int mid = (start + end) >> 1;
        return mergeTwoLists(mergeKPartitionwoLists(lists, start, mid), mergeKPartitionwoLists(lists, mid + 1, end));
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode tail = res;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                tail.next = l2;
                break;
            }
            if (l2 == null) {
                tail.next = l1;
                break;
            }
            if (l1.val < l2.val) {
                tail.next = new ListNode(l1.val);
                tail = tail.next;
                l1 = l1.next;
            } else if (l1.val > l2.val) {
                tail.next = new ListNode(l2.val);
                tail = tail.next;
                l2 = l2.next;
            }
        }
        return res.next;
    }


    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(x -> x.val));
        for (ListNode list : lists) {
            if (list != null) {
                priorityQueue.add(list);
            }
        }
        ListNode l = new ListNode(0);
        ListNode s = l;
        while (!priorityQueue.isEmpty()) {
            ListNode f = priorityQueue.poll();
            s.next = f;
            s = s.next;
            if (s.next != null) {
                priorityQueue.offer(s.next);
            }
        }
        return l.next;
    }

}
